package com.tucc.hello.leetcode.no1_400.no1_200.no61_80.no74;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] matrix = {{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
        System.out.println(solution.searchMatrix(matrix, 60));
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int left = 0;
        int h = matrix.length;
        int w = matrix[0].length;
        int right = h * w - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            int cur = matrix[mid / w][mid % w];
            if (cur == target) {
                return true;
            }
            if (cur < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}
